#include "grid.h"

void Grid::initializeRouter() {
	// adjust sizes of vectors
	routeTerminals.resize(squareSide+1); //channels, as many as cell rows + 1
	terminalRowSize = (squareSide*2)+maxFeedthrough;
	// adjust if less Feedthroughs needed than cells
	if (terminalRowSize < (squareSide*3)+1) {
		terminalRowSize = (squareSide*3)+1;
	}
	for(unsigned int i = 0; i < routeTerminals.size(); i++) {
		routeTerminals[i].first.resize(terminalRowSize); // each row as number of cells * 2 plus feedthrough # terminals
		routeTerminals[i].second.resize(terminalRowSize);
	}
	routeChannels.resize(squareSide+1); // know number of channels
	for(unsigned int i = 0; i < routeChannels.size(); i++) { // initialize number of rows in each channel to 0
		routeChannels[i].resize(0);
	}
	VCG.resize(squareSide+1);
	routeNetlist.resize(squareSide+1);
	// calculate feedthough variables
	middleFeeds = maxFeedthrough-(squareSide+1); // number of feedthroughs to have stacked in middle
	if(middleFeeds < 0) {
		middleFeeds = 0;
	}
	middleFeedStart = squareSide/2; // location that middle feeds will start at
	// build routeTerminals array
	// BOZO: this will fail if there are actually more than one net per terminal
	for(CellType i = 0; i < squareSide; i++) { // row of cells
		CellType j = 0; // keep track of where in row
		// put in first feedthrough
		addFeedthrough(i,j);
		// put in cellTerminals
		for(CellType k = 0; k <= middleFeedStart; k++) { // first set of alternating cells/feedthroughs
			CellType index = cellGrid[i][k];
			// add cell terminals
			initCellTerms(index, i, j);
			// put in feedthrough
			addFeedthrough(i,j);
		}
		// put in middle feedthroughs
		for(CellType k = 0; k < middleFeeds; k++) {
			addFeedthrough(i,j);
		}
		// put in cells after feedthrough
		for(CellType k = middleFeedStart+1; k < squareSide; k++) {
			CellType index = cellGrid[i][k];
			// add cell terminals
			initCellTerms(index, i, j);
			// put in feedthrough
			addFeedthrough(i,j);
		}
	}
}

void Grid::initCellTerms(CellType index, CellType i, CellType &j) {
	if (index >= 0) { // cell is not a vacant cell
		if (cells[index].flip) { // cell is flipped
			// add these to bottom of channel
			for(unsigned short int l = 0; l < cells[index].terminal[2].size(); l++) {
				routeTerminals[i].second[j] = cells[index].terminal[2][l];
			}
			for(unsigned short int l = 0; l < cells[index].terminal[3].size(); l++) {
				routeTerminals[i].second[j+1] = cells[index].terminal[3][l];
			}
			// add these to top of channel
			for(unsigned short int l = 0; l < cells[index].terminal[0].size(); l++) {
				routeTerminals[i+1].first[j] = cells[index].terminal[0][l];
			}
			for(unsigned short int l = 0; l < cells[index].terminal[1].size(); l++) {
				routeTerminals[i+1].first[j+1] = cells[index].terminal[1][l];
			}
		}
		else { // cell is not flipped
			// add these to bottom of channel
			for(unsigned short int l = 0; l < cells[index].terminal[0].size(); l++) {
				routeTerminals[i].second[j] = cells[index].terminal[0][l];
			}
			for(unsigned short int l = 0; l < cells[index].terminal[1].size(); l++) {
				routeTerminals[i].second[j+1] = cells[index].terminal[1][l];
			}
			// add these to top of channel
			for(unsigned short int l = 0; l < cells[index].terminal[2].size(); l++) {
				routeTerminals[i+1].first[j] = cells[index].terminal[2][l];
			}
			for(unsigned short int l = 0; l < cells[index].terminal[3].size(); l++) {
				routeTerminals[i+1].first[j+1] = cells[index].terminal[3][l];
			}
		}
		j+=2;
	}
	else {	// cell is vacant cell
		// leave vacant
		// BOZO: replace with feedthroughs?
		j+=2;
	}
}

void Grid::addFeedthrough(CellType cellRow, CellType &cellCol) {
	routeTerminals[cellRow].second[cellCol].setCellNode(-1, -1, -1); // top of cellRow is bottom of channel
	routeTerminals[cellRow+1].first[cellCol].setCellNode(-1, -1, -1);
	cellCol++;
}

void Grid::initializeFeedthroughs() {
	map<CellType,TerminalNode>::iterator it;
	CellType totalFeedthrough_test = 0;
	for(it = feedthroughList.begin(); it != feedthroughList.end(); it++) { // for each feedthrough net
		// find the direction of net from cell
		// find "nearest" available feedthrough cell
		// apply netNum to feedthrough cell terminals vertical length needed

		// BOZO: doesn't work for more than one net per term
		PositionType start, end;
		bool dir; // horizontal direction from start to end, false=left
		CellType startCell; // horizontal index of start cell
		vertHeightCalc(it->second.cellNum, it->second.termNum, 0, start, end, dir, startCell);
		CellType index = routeIndex(cells[startCell].position[0]);
		for(PositionType l = start; l <= end; l++) {
			// need to pick a feedthrough cell for each of these rows
			index = chooseFeedthroughCell(index, l, dir);
			routeTerminals[l].second[index].netNum = it->second.netNum;
			routeTerminals[l+1].first[index].netNum = it->second.netNum;
		}
		totalFeedthrough_test += (end-start+1);
	}
	cerr << "Total Feedthroughs Added: " << totalFeedthrough_test << endl;
}

CellType Grid::chooseFeedthroughCell(CellType preferIndex, PositionType cellRow, bool dir) {
	CellType feedIndex = preferIndex, finalIndex;
	PositionType channelRow = cellRow;
	bool last = false;
	// if cellRow is the last row, then use top of channel, otherwise use bottom
	if(cellRow == squareSide-1) {
		channelRow = cellRow+1;
		last = true;
	}

	bool found = false;
	while(!found) {
		if(!last) {
			if(routeTerminals[channelRow].second[feedIndex].netNum == -1) {
				// this is a feedthrough cell, and it is vacant
				found = true;
				finalIndex = feedIndex;
			}
		}
		else {
			if(routeTerminals[channelRow].first[feedIndex].netNum == -1) {
				// this is a feedthrough cell, and it is vacant
				found = true;
				finalIndex = feedIndex;
			}
		}

		// move to next terminal
		if(dir) {
			feedIndex++;
			if(feedIndex >= terminalRowSize) {
				feedIndex = preferIndex;
				dir = false;
			}
		}
		else {
			feedIndex--;
			if(feedIndex < 0) {
				feedIndex = preferIndex;
				dir = true;
			}
		}
	}
	
	return finalIndex;
}

CellType Grid::routeIndex(CellType index) {
	// returns the horizontal routing index of a cell in the grid
	CellType routeIndex = -1;
	routeIndex = (index*3); // first cell is feedthrough
	if(index > middleFeedStart) { // adjust if after the middle feeds
		routeIndex += middleFeeds;
	}
	return routeIndex;
}

void Grid::createVCG(CellType index) {
	// add each set of terminals to VCG, only if both terminals exist
	// the VCG is a multimap, with key being a netNum and all nodes above it (it is dependent on) in vcg as data
	for(unsigned short int i = 0; i < routeTerminals[index].first.size(); i++) {
		// add to VCG if necessary
		if((routeTerminals[index].first[i].netNum >= 0) && (routeTerminals[index].second[i].netNum >= 0)) {
			VCG[index].insert(pair<CellType,CellType>(routeTerminals[index].second[i].netNum, routeTerminals[index].first[i].netNum));
		}
		// add to list of nets in this channel
		// add all since they won't get added multiple times
		if(routeTerminals[index].first[i].netNum >= 0) {
			routeNetlist[index].insert(pair<CellType,CellType>(routeTerminals[index].first[i].netNum, routeTerminals[index].first[i].netNum));
		}
		if(routeTerminals[index].second[i].netNum >= 0) {
			routeNetlist[index].insert(pair<CellType,CellType>(routeTerminals[index].second[i].netNum, routeTerminals[index].second[i].netNum));
		}
	}
}

CellType Grid::rowFit(CellType channel, PositionType start, PositionType end ) {
	// returns the row where trunk will fit
	TrunkNode newNode(0, start, end, true, true);
	bool collision = false;
	for ( unsigned short int i = 0; i < routeChannels[channel].size(); i++) {  // for each row in channel
		collision = false;
		for ( unsigned short int j = 0; j < routeChannels[channel][i].size(); j++) { // for each terminal in row
			if(newNode.collide(routeChannels[channel][i][j])) {
				// need to try next row
				collision = true;
			}
			if((j == routeChannels[channel][i].size()-1) && !collision) {
				// made it through entire row and no collision, will fit here
				return i;
			}
		}
	}
	// no current rows found where this will fit, add new row, return index to that row
	ChannelRowType newRow;
	newRow.resize(0);
	routeChannels[channel].push_back(newRow);
	return (CellType) (routeChannels[channel].size()-1);
}

void Grid::calcNet(CellType channel, CellType netNum, PositionType &start, PositionType &end, bool &start_up, bool &end_up) {
	// search through top list and bottom list
	CellType index0 = -1, index1 = -1, indexCount = 0;
	bool index0_up, index1_up;
	// search top
	for(unsigned short int i = 0; i < routeTerminals[channel].first.size(); i++) {
		if(routeTerminals[channel].first[i].netNum == netNum) {
			// net is connected to this terminal
			if(index0 == -1) {
				// index0 not found yet
				index0 = i;
				index0_up = true;
			}
			else {
				// index0 already found, this is last terminal
				index1 = i;
				index1_up = true;
				// BOZO: can exit loop here
			}
		}
	}
	// search bottom
	for(unsigned short int i = 0; i < routeTerminals[channel].second.size(); i++) {
		if(routeTerminals[channel].second[i].netNum == netNum) {
			// net is connected to this terminal
			if(index0 == -1) {
				// index0 not found yet
				index0 = i;
				index0_up = false;
			}
			else {
				// index0 already found, this is last terminal
				index1 = i;
				index1_up = false;
				// BOZO: can exit loop here
			}
		}
	}
	
	// calculate for start/end
	if((index0-index1) < 0) {
		// index0 is before index1 (left)
		start = index0;
		start_up = index0_up;
		end = index1;
		end_up = index1_up;
	}
	else {
		// index0 is after index1 (right)
		start = index1;
		start_up = index1_up;
		end = index0;
		end_up = index0_up;
	}

}

CellType Grid::nextNet(CellType channel) {
	// choose the first value in the netlist
	NetlistType::iterator net = routeNetlist[channel].begin();
//	pair<VCGmap::iterator,VCGmap::iterator> dependencyRange;
//	VCGmap::iterator it = VCG[channel].begin();
	// Check to see if it has any constraints
//	dependencyRange = VCG[channel].equal_range(it->first);
	//VCG[channel];
	return net->first;
}

void Grid::router() {
	for ( unsigned short int i = 0; i < squareSide+1; i++) {  // for each channel
		cerr << ".";
		// create VCG
		createVCG(i);
	// route each net
		unsigned short int totalNets = routeNetlist[i].size();
		for( unsigned short int j = 0; j < totalNets; j++) {
			// loop through as many nets as there are, not necessarily in order
			CellType netNum = nextNet(i);
			// Calculate the start and stop point of the net, and direction
			PositionType start = 0, end = 0;
			bool start_up = false, end_up = false;
			calcNet(i, netNum, start, end, start_up, end_up);
			// Check for where the insertion of trunk will be made
			CellType rowIndex = rowFit(i, start, end);
			// insert into that row
			TrunkNode newNode(netNum, start, end, start_up, end_up);
			routeChannels[i][rowIndex].push_back(newNode);
			// remove from net list
			routeNetlist[i].erase(netNum);
		}
	}
}

void Grid::route() {
	cerr << "Initializing terminals..." << endl;
	initializeRouter();
	cerr << "Initializing feedthrough terminals..." << endl;
	initializeFeedthroughs();
	cerr << "Routing";
	router();
	cerr << endl;
}